This invention relates to digital data processing and, more particularly, to methods and apparatus for database management systems on multiprocessor digital data processing systems.
In addition to performing calculations, computers have traditionally been used to store and retrieve large amounts of data. Early computer systems were typically programmed for this on an ad hoc basis. For example, to track a company's employees, a program was typically written to handle all steps necessary to input, sort and store employee data in a computer file and, as necessary, to retrieve and collate it to generate reports. Special-purpose software packages, referred to as database management systems (or "DBMS's"), were later developed to handle all but the highest-level of these tasks.
Among the most widely used database management systems are the so-called relational systems. From an operator's perspective, these store data in two-dimensional tables. For example, each row (or record) of an employee data table might include the following columns (or fields) of information: name of an employee, his or her identification number, address, and department number.
. . . . . . . . . . . . Smith 1056 5 Oak Avenue 10 James 1058 3 State Street 41 Wright 1059 15 Main Street 25 . . . . . . . . . . . .
One or more indexes on large tables are generally provided to facilitate the most common data accesses, e.g., look-ups based on employee name.
In relational systems, corresponding rows in two or more tables are identified by matching data values in one or more columns. For example, the department name corresponding to a given employee may be identified by matching his or her department number to a row in a department data table that gives department numbers and department names. This is in contrast to hierarchical, network, and other DBMS's that use pointers instead of data values to indicate corresponding rows when tables are combined, or "joined."
Relational DBMS's typically permit the operator to access information in the database via a query. This is a command that specifies which data fields (columns) are to be retrieved from a database table and which records (rows) those fields are to be selected from. For example, a query for the names of all employees in department 10 might be fashioned as follows:
 SELECT name, department_number FROM employee WHERE department_number = 10
There is no particular ordering of the resulting rows retrieved by the DBMS, unless the query specifies an ordering (e.g., ORDER BY name).
A query may also involve multiple tables. For example, to retrieve department names instead of numbers, the above query might be refashioned as follows:
 SELECT name, department_name FROM employee, department WHERE department_number = 10 AND employee.department_number=department.department_number
A particular relational data table need not be stored in a single computer file but, rather, can be partitioned among many files. This makes such tables particularly suited for use on multiprocessor computer systems, i.e., computer systems having multiple processors and multiple disk drives (or other storage devices) of the type disclosed in U.S. Pat. No. 5,055,999. Unfortunately, prior art DBMS's have not proven capable of taking full advantage of the power of such multiprocessing systems and, particularly, their power to simultaneously process data (in parallel) from multiple partitions on multiple storage devices with multiple central processing units.
In view of the foregoing, an object of the invention is to provide improved methods and apparatus for database management and, particularly, improved methods and apparatus for data base management capable of operating on multiprocessor systems.
A further object of the invention is to provide improved systems for database management capable of effectively accessing a relational database contained in multiple tables and multiple partitions.
A still further object is to provide improved methods and apparatus for storing and retrieving data for access by a DBMS.
These and other objects are evident in the attached drawings and the description which follows.